package all;

import leetcodeHis.ListNode;

import java.util.*;

/**
 * @Author zhang lei
 * @Date 2022-01-21 17:25
 */
public class Test1TO50 {

    public static void main(String[] args) {
        System.out.println(longestPalindrome1("abba"));

        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(9);

        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);
        l2.next.next.next = new ListNode(9);

        l1 = new Test1TO50().addTwoNumbers(l1,l2);
        System.out.println(l1);
    }

    /**
     * 第4题, 【最长回文子串】
     * @param s
     * @return
     */
    public static String longestPalindrome(String s) {
        if(s.length()<2) {
            return s;
        }


        //超时版本
//        for (int i = 0; i < s.length(); i++) {
//            for (int j = i+1; j < s.length(); j++) {
//                if(isPalindome(s, i, j) && j-i+1>max) {
//                    max = Math.max(max, j-i+1);
//                    maxStr = s.substring(i,j+1);
//                }
//            }
//        }
        boolean[][] arr = new boolean[s.length()][s.length()];
        int max = 0;
        String result = "";

        for (int len = 1; len <= s.length(); len++) {
            for (int start = 0; start < s.length(); start++) {
                int end = start+len - 1;
                if(end>=s.length()) {
                    break;
                }
                //动态规划算法  arr[start+1][end-1] 表示 arr[start][end] 的子串
                arr[start][end] = ((len==1 || len==2 || arr[start+1][end-1])) && s.charAt(start) == s.charAt(end);
                if(arr[start][end]) {
                    result = s.substring(start, end+1);
                }
            }
        }
        System.out.println(Arrays.deepToString(arr));
        return result;
    }

    private static boolean isPalindome(String s, int l, int r) {
        while (l<=r) {
            if(s.charAt(l++) != s.charAt(r--)) {
                return false;
            }
        }
        return true;
    }

    public static String longestPalindrome1(String s) {
        //第一种方法一定是 O(n^2)复杂度的
        //动态规划，建立数组
        boolean[][] arr = new boolean[s.length()][s.length()];

        String result = "";
        for (int len = 1; len <= s.length(); len++) {
            for (int start = 0; start < s.length(); start++) {
                int end = start+len-1;
                if(end>s.length()-1) {
                    break;
                }
                arr[start][end] = (len ==1 || len== 2|| arr[start+1][end-1] ) && s.charAt(start) == s.charAt(end);
                if(arr[start][end]) {
                    result = s.substring(start, end+1);
                }

            }
        }

        return result;

    }

    //位图，滑动窗口
    //基本思想，如果map中没有，就放入， r++； 如果map中有，就 remove(l++),  长度就行  r-l+1
    public static int lengthOfLongestSubstring1(String s) {
        if(s.length() == 0) {
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();

        int l=0, r=0, max = 0;
        while (r<s.length()) {
            Character lc = s.charAt(r);
            if(map.get(lc) == null) {
                map.put(lc, r);
                max = Math.max(max, r-l+1);
                r++;
            }else {
                map.remove(s.charAt(l++));
            }
        }
        return max;
    }

    public static int lengthOfLongestSubstring0(String s) {
        if(s.length() == 0) {
            return 0;
        }
        BitSet bitSet = new BitSet(256);

        int l=0, r=0, max = 0;
        while (r<s.length()) {
            Character lc = s.charAt(r);
            if(!bitSet.get(lc)) {
                bitSet.set(lc);
                max = Math.max(max, r-l+1);
                r++;
            }else {
                bitSet.clear(s.charAt(l++));
            }
        }
        return max;
    }

    public static int lengthOfLongestSubstring2(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int l = 0, result = 0;

        for(int i=0;i<s.length();i++) {
            char cur = s.charAt(i);
            if(map.get(cur) == null) {
                map.put(cur, i);
                if(i == s.length() -1) {
                    return Math.max(map.size(), result);
                }
            }else {
                int index = map.get(cur);
                result = Math.max(result, i-l);
                l = index+1;
                removeIndex(index,map);
                map.put(cur, i);
            }
        }
        return result;
    }

    /**
     * O(n^2)
     * @param index
     * @param map
     */
    private static void removeIndex(int index, Map<Character, Integer> map) {
        List<Character> list = new ArrayList<>();
        for (Map.Entry<Character, Integer> e : map.entrySet()) {
            if(e.getValue()<index) {
                list.add(e.getKey());
            }
        }
        for (Character character : list) {
            map.remove(character);
        }
    }

    /**
     * 1、两数之和
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
//        for (int i = 0; i < nums.length-1; i++) {
//            for (int j = i+1; j < nums.length; j++) {
//                if(nums[i] + nums[j] == target) {
//                    return new int[]{i,j};
//                }
//            }
//        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int cur = nums[i];
            if(map.get(target-cur) != null) {
                return new int[]{i, map.get(target-cur)};
            }
            map.put(cur,i);
        }
        return new int[]{0,0};
    }

    /**
     * 2、两数相加
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result = new ListNode(-1);
        ListNode head = result;
        int temp = 0;
        while (l1 != null || l2 != null) {
            int sum = (l1 == null? 0: l1.val) + (l2 == null? 0:l2.val) + temp;
            l1 = l1 == null? null : l1.next;
            l2 = l2 == null? null : l2.next;
            temp = sum/10;
            head.next = new ListNode( sum%10);
            head = head.next;
        }

        if(temp>0) {
            head.next = new ListNode(1);
        }
        return result.next;
    }

    /**
     * 3、无重复最长子串
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        if(s.length() == 0 || s.length() ==1) {
            return s.length();
        }
        int result = 0;
        Map<Character, Integer> map = new HashMap<>();
        int index = 0;
        for (int i = 0; i < s.length(); i++) {
            char cur = s.charAt(i);
            if(map.get(cur) == null) {
                map.put(cur, i);
                result = Math.max(result, map.size());
            }else {
                int end = map.get(cur);
                while (index<=end) {
                    map.remove(s.charAt(index++));
                }
                map.put(cur, i);
            }
        }
        return result;
    }
}
